package com.czh.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 树的操作
 *
 * @author chenzhihua
 * @Date 2024/2/21
 */
public class BaseOperateTree {
    public static void main(String[] args) {
        //1. 初始化二叉树
        TreeNode treeNode = createTreeNode();
//        insertAndRemoveTreeNode(treeNode);
//        List<TreeNode> treeNodes = binary_tree_bfs(treeNode);
//        treeNodes.forEach(treeNode1 -> System.out.print(treeNode1.val + "->"));

        System.out.println(preOrder(treeNode));
    }

    //1. 初始化二叉树
    public static TreeNode createTreeNode() {
        // 初始化节点
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);
        TreeNode n4 = new TreeNode(4);
        TreeNode n5 = new TreeNode(5);
        // 构建节点之间的引用（指针）
        n1.left = n2;
        n1.right = n3;
        n2.left = n4;
        n2.right = n5;
        return n1;
    }

    //2.  插入与删除节点
    public static TreeNode insertAndRemoveTreeNode(TreeNode treeNode) {
        // 添加p节点
        TreeNode p = new TreeNode(0);
        // 保存当前数的做左节点
        TreeNode left = treeNode.left;
        treeNode.left = p;
        p.left = left;
        // 移除p节点
        treeNode.left = left;
        return treeNode;
    }

    //3. 遍历
    // 1) 广度优先遍历:遵循“逐层推进”的规则所以用队列实现
    public static List<TreeNode> binary_tree_bfs(TreeNode treeNode) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(treeNode);
        List<TreeNode> list = new ArrayList<>();
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            list.add(poll);
            if (poll.left != null) {
                // 左节点进队列
                queue.offer(poll.left);
            }
            if (poll.right != null) {
                //右节点进队列
                queue.offer(poll.right);
            }
        }
        return list;
    }

    //2) 前序(根左右)、中序(左根右)、后序遍历(左右根)
    public static List<Integer> preOrder(TreeNode treeNode) {
        List<Integer> result = new ArrayList<>();
        result.add(treeNode.val);
        if (treeNode.left != null) {
            result.addAll(preOrder(treeNode.left));
        }
        if (treeNode.right != null) {
            result.addAll(preOrder(treeNode.right));
        }
        return result;
    }

    // 二叉搜索树的操作
    //1.   查找节点
    public static TreeNode searchTreeNode(TreeNode treeNode, int num) {
        while (treeNode != null) {
            if (treeNode.val > num) {
                treeNode = treeNode.right;
            } else if (treeNode.val < num) {
                treeNode = treeNode.left;
            } else {
                break;
            }
        }
        return treeNode;
    }

    //2.   插入节点
    public static void insertTreeNode(TreeNode treeNode, int num) {
        // cur插入的位置，pre插入的父节点
        TreeNode cur = treeNode, pre = null;
        while (cur != null) {
            // 如果存在重复元素则直接返回
            if (cur.val == num) {
                return;
            }
            // 保存前一个元素
            pre = cur;
            if (cur.val > num) {
                cur = cur.right;
            } else {
                cur = cur.left;
            }
        }
        // 执行插入操作
        TreeNode node = new TreeNode(num);
        if (pre.val > num) {
            pre.left = node;
        } else {
            pre.right = node;
        }
    }

    //3.   删除节点
    public static void removeTreeNode(TreeNode treeNode, int num) {
        // 先找到当前节点和当前节点的父节点
        if (treeNode == null) {
            return;
        }
        TreeNode cur = treeNode, pre = null;
        while (cur != null) {
            if (cur.val == num) {
                break;
            }
            pre = cur;
            if (cur.val > num) {
                cur = cur.right;
            }
            if (cur.val < num) {
                cur = cur.left;
            }
        }
        // 未找到需要删除的节点
        if (cur == null) {
            return;
        }
        // 子节点数0/1  直接删除，或者将子节点赋值给当前节点
        if (cur.left == null || cur.right == null) {
            TreeNode child = cur.left == null ? cur.right : cur.left;
        }
    }
}

class TreeNode {
    int val; // 节点值
    TreeNode left; // 左节点
    TreeNode right; // 右节点

    public TreeNode(int val) {
        this.val = val;
    }

    @Override
    public String toString() {
        return super.toString();
    }
}